package com.bascker.algorithm.practice.str;

import java.util.Objects;

/**
 * 最长公共前缀: 查找字符串数组中的最长公共前缀，若不存在公共前缀，返回空字符串 ""。
 *
 * For example:
 *   in: ["flower","flow","flight"]    out: "fl"
 *   in: ["dog","racecar","car"]       out: ""
 *
 * @apiNote leetcode T4
 * @implNote https://gitee.com/bascker/algorithm/wikis/5%E3%80%81%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%89%8D%E7%BC%80?sort_id=2976764
 * @author bascker
 */
public class LongestCommonPrefix {

    public String longestCommonPrefix(String[] strs) {
        if (Objects.isNull(strs) || strs.length == 0) {
            return "";
        }

        int n = strs.length;

        // 使用 rs 跟踪最长公共前缀
        String rs = strs[0];
        for (int i = 1; i < n; ++i) {
            String x = strs[i];

            // 若 x 就是 rs 的前缀，则 x 赋值给 rs
            if (rs.startsWith(x)) {
                rs = x;
                continue;
            }

            int len = Math.min(rs.length(), x.length());
            for (int j = 0; j < len; ++j) {
                if (rs.charAt(j) != x.charAt(j)) {
                    rs = rs.substring(0, j);
                    break;
                }
            }
        }

        return rs;
    }

}
